/**
 * Copyright (c) 2017-2024 Nop Platform. All rights reserved.
 * Author: canonical_entropy@163.com
 * Blog:   https://www.zhihu.com/people/canonical-entropy
 * Gitee:  https://gitee.com/canonical-entropy/nop-entropy
 * Github: https://github.com/entropy-cloud/nop-entropy
 */
package com.gitee.wsl.struct.table

import com.gitee.wsl.ext.base.compare
import kotlin.math.max
import kotlin.math.min

class CellRangeMerger {
    internal class Range {
        var firstIndex: Int
        var lastIndex: Int

        constructor(index: Int) {
            this.lastIndex = index
            this.firstIndex = this.lastIndex
        }

        constructor(firstIndex: Int, lastIndex: Int) {
            this.firstIndex = firstIndex
            this.lastIndex = lastIndex
        }

        fun copy(): Range {
            return Range(firstIndex, lastIndex)
        }
    }

    internal class Block {
        var firstRowIndex: Int
        var lastRowIndex: Int
        var firstColIndex: Int
        var lastColIndex: Int

        constructor(range: Range, colIndex: Int) {
            this.firstRowIndex = range.firstIndex
            this.lastRowIndex = range.lastIndex
            this.lastColIndex = colIndex
            this.firstColIndex = this.lastColIndex
        }

        constructor(firstRowIndex: Int, lastRowIndex: Int, colIndex: Int) {
            this.firstRowIndex = firstRowIndex
            this.lastRowIndex = lastRowIndex
            this.lastColIndex = colIndex
            this.firstColIndex = this.lastColIndex
        }

        constructor(firstRowIndex: Int, lastRowIndex: Int, firstColIndex: Int, lastColIndex: Int) {
            this.firstRowIndex = firstRowIndex
            this.lastRowIndex = lastRowIndex
            this.firstColIndex = firstColIndex
            this.lastColIndex = lastColIndex
        }


        override fun toString(): String {
            return toCellRange().toString()
        }

        fun toCellRange(): CellRange {
            return CellRange(firstRowIndex, firstColIndex, lastRowIndex, lastColIndex)
        }
    }

    /**
     * 按照列映射到排好序的区间列表中
     */
    private val colRanges: MutableMap<Int,MutableList<Range>> = mutableMapOf()
    private var minRowIndex = Int.MAX_VALUE
    private var maxRowIndex = -1
    private var minColIndex = Int.MAX_VALUE
    private var maxColIndex = -1

    fun display(): String {
        val sb= StringBuilder()
        val n = maxRowIndex + 1
        val m = maxColIndex + 1

        for (i in 0 until n) {
            if (i != 0) sb.append('\n')
            for (j in 0 until m) {
                sb.append('0')
            }
        }

        colRanges.forEach {(colIndex,list)->
            for (range in list) {
                for (i in range.firstIndex..range.lastIndex) {
                    val pos: Int = i * (m + 1) + colIndex
                    sb[pos] = '1'
                }
            }
        }
        return sb.toString()
    }

    val mergedRanges: List<CellRange>
        get() {
            val ret: MutableList<CellRange> = ArrayList<CellRange>()

            val blocks: MutableList<Block> = ArrayList<Block>()

            for (colIndex in minColIndex..maxColIndex) {
                val list = colRanges[colIndex]
                if (list == null) {
                    // 没有可合并的列
                    toRanges(blocks, ret)
                } else {
                    var index = 0
                    for (range in list) {
                        val r = range.copy()
                        do {
                            index = mergeRange(index, colIndex, r, blocks, ret)
                            if (index < 0) {
                                index = -index
                                break
                            }
                        } while (true)
                    }
                }
            }
            toRanges(blocks, ret)
            return ret
        }

    private fun mergeRange(
        index: Int,
        colIndex: Int,
        range: Range,
        blocks: MutableList<Block>,
        ret: MutableList<CellRange>
    ): Int {
        var i = index
        while (i < blocks.size) {
            val block = blocks[i]
            if (range.firstIndex > block.lastRowIndex) {
                val completed = blocks.removeAt(i)
                ret.add(completed.toCellRange())
                i--
                i++
                continue
            }

            if (range.lastIndex < block.firstRowIndex) {
                // range与block不重叠
                val prev = Block(range, colIndex)
                blocks.add(i, prev)
                return -(i + 1)
            } else if (range.firstIndex <= block.firstRowIndex) {
                if (range.firstIndex < block.firstRowIndex) {
                    // range与block重叠，需要拆分区间
                    val block1 = Block(range.firstIndex, block.firstRowIndex - 1, colIndex)
                    blocks.add(i, block1)
                    i++
                }
                if (range.lastIndex < block.lastRowIndex) {
                    // block的前半部分与range合并
                    val block2 =
                        Block(block.firstRowIndex, range.lastIndex, block.firstColIndex, colIndex)
                    blocks.add(i, block2)
                    i++
                    // 缩减block的部分
                    block.firstRowIndex = range.lastIndex + 1
                } else if (range.lastIndex == block.lastRowIndex) {
                    block.lastColIndex++
                } else {
                    block.lastColIndex++
                    // 缩减range，尝试下一个block
                    range.firstIndex = block.lastRowIndex + 1
                    return i + 1
                }
                return -(i + 1)
            } else {
                // block.firstRowIndex < range.firstIndex <= block.lastRowIndex
                val block1: CellRange = CellRange(
                    block.firstRowIndex,
                    block.firstColIndex,
                    range.firstIndex - 1,
                    block.lastColIndex
                )
                ret.add(block1)
                if (range.lastIndex < block.lastRowIndex) {
                    val block2 =
                        Block(range.firstIndex, range.lastIndex, block.firstColIndex, colIndex)
                    blocks.add(i, block2)
                    block.firstRowIndex = range.lastIndex + 1
                    return -(i + 1)
                } else if (range.lastIndex == block.lastRowIndex) {
                    block.firstRowIndex = range.firstIndex
                    block.lastColIndex++
                    return -(i + 1)
                } else {
                    // range.lastIndex > block.lastRowIndex
                    block.firstRowIndex = range.firstIndex
                    block.lastColIndex++
                    range.firstIndex = block.lastRowIndex + 1
                    return i + 1
                }
            }
            i++
        }

        val next = Block(range, colIndex)
        blocks.add(next)
        return -blocks.size
    }

    private fun toRanges(blocks: MutableList<Block>, ret: MutableList<CellRange>) {
        for (block in blocks) {
            ret.add(block.toCellRange())
        }
        blocks.clear()
    }

    fun addCell(rowIndex: Int, colIndex: Int) {
        this.minRowIndex = min(minRowIndex.toDouble(), rowIndex.toDouble())
            .toInt()
        this.minColIndex = min(minColIndex.toDouble(), colIndex.toDouble())
            .toInt()
        this.maxRowIndex = max(maxRowIndex.toDouble(), rowIndex.toDouble())
            .toInt()
        this.maxColIndex = max(maxColIndex.toDouble(), colIndex.toDouble())
            .toInt()

        var list = colRanges[colIndex]
        if (list == null) {
            list = ArrayList<Range>()
            colRanges.put(colIndex, list)

            val range = Range(rowIndex)
            list.add(range)
        } else {
            val idx = binarySearch(list, rowIndex)
            // 如果找到匹配单元，则已经存在，可以直接忽略。
            // 如果不存在，则考虑是延展已有的区间，还是插入新的区间
            if (idx < 0) {
                val low = -idx - 1
                if (low > 0) {
                    val prev = list[low - 1]
                    if (prev != null) {
                        if (prev.lastIndex >= rowIndex) return
                        if (prev.lastIndex + 1 == rowIndex) {
                            // 延展前方的区间
                            prev.lastIndex++

                            if (low < list.size) {
                                val next = list[low]
                                // 与后一个区间合并
                                if (next != null && next.firstIndex == prev.lastIndex) {
                                    prev.lastIndex = next.lastIndex
                                    list.removeAt(low)
                                }
                            }
                            return
                        }
                    }
                }

                if (low + 1 < list.size) {
                    val next = list[low + 1]
                    if (next != null) {
                        // 此时前方区间肯定不会与next进行合并
                        if (next.firstIndex == rowIndex + 1) {
                            next.firstIndex = rowIndex
                            return
                        }
                    }
                }
                val range = Range(rowIndex)
                list.add(low, range)
            }
        }
    }

    private fun binarySearch(list: List<Range>, rowIndex: Int): Int {
        var low = 0
        var high = list.size - 1

        while (low <= high) {
            val mid = (low + high) ushr 1
            val midVal = list[mid]
            val cmp: Int = midVal.firstIndex.compare(rowIndex)

            if (cmp < 0) low = mid + 1
            else if (cmp > 0) high = mid - 1
            else return mid // key found
        }
        return -(low + 1) // key not found
    }
}
